package secondary

import "math"

/*
	我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
	示例:

	输入: n = 10
	输出: 12
	解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
	说明:

	1是丑数。
	n不超过1690。

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/chou-shu-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/*
	每一个丑数都只能是小于它的丑数与质因子的乘积
*/
func NthUglyNumber(n int) int {
	return nthUglyNumber(n)
}
func nthUglyNumber(n int) int {
	f2, f3, f5 := 2, 3, 5 // 质因子
	if n <= 2 {
		return n
	}
	dp := make([]int, n)
	dp[0] = 1
	for i := 1; i < len(dp); i++ {
		minUgly := math.MaxInt32
		for j := 0; j < i; j++ {
			if dp[j]*f2 > dp[i-1] {
				minUgly = min(minUgly, dp[j]*f2)
			}
			if dp[j]*f3 > dp[i-1] {
				minUgly = min(minUgly, dp[j]*f3)
			}
			if dp[j]*f5 > dp[i-1] {
				minUgly = min(minUgly, dp[j]*f5)
			}
		}
		dp[i] = minUgly
	}
	return dp[len(dp)-1]
}
